Theo truyền thuyết làng Khoai xưa, tức làng Minh Khai ở thị trấn Như Quỳnh (Văn Lâm, Hưng Yên) nay là quê hương sứ quân Lữ Đường.[1] Thuở nhỏ ông còn có tên gọi khác là Lữ Tá Phi vốn người cao lớn, thông minh, văn võ song toàn. Ông được sinh ra năm 927, trong một gia đình hào trưởng giàu có, cha ông là Lữ Đại Liệu, nguyên là bộ tướng của sứ quân Trần Lãm và đã lập được nhiều chiến công dưới thời Ngô Quyền. Lớn lên ông kế nghiệp cha lập ấp và cai trị nhân dân khu vực Tế Giang (nay là khu vực các huyện phía bắc Hưng Yên). Gặp thời loạn, thế lực của ông nổi lên trở thành một trong những đại diện cát cứ mạnh nhất thời 12 sứ quân.

Làng Khoai nằm cách đình Bến ở huyện Văn Giang, nơi được cho là lỵ sở của ông khi xưa khoảng 9 km. Cũng theo truyền thuyết khu vực Tế Giang, trong một lần đánh giặc, ông bị thương ở tay và được một người con gái làng chài cứu chữa vì cảm động mà lấy người đó làm vợ. Bà phu nhân sinh cho ông một con trai tài giỏi, tinh thông võ nghệ, sống hào hiệp, được người dân mến mộ. Lữ Lang sau được Lê Hoàn giao là tướng trấn giữ phòng tuyến bờ Bắc sông Lục Giang trong kháng chiến chống Tống năm 981.